package com.cuz.daileetcode;

import jdk.nashorn.internal.runtime.regexp.joni.constants.StackType;

import java.util.ArrayList;
import java.util.List;

public class Day61 {


    public static class FindNumbersThatDontPear {
        public static void main(String[] args) {
            List<Integer> integers = solution1(new int[]{8, 5, 1, 2, 6, 6, 6, 7});
            System.out.println(integers);
        }

        public static List<Integer> solution1(int[] arr) {
            for (int index = 0; index < arr.length; index++) {
                if (arr[index] != index + 1) {
                    swapToOriginalLocation(arr, index);
                }
            }
            ArrayList<Integer> res = new ArrayList<>();
            for (int index = 0; index < arr.length; index++) {
                if (arr[index] != index + 1) {//
                    //                res.add(arr[index]);
                    res.add(index + 1);
                }
            }
            return res;
        }

        private static void swapToOriginalLocation(int[] arr, int index) {
            //这个位置的数
            int valueError = arr[index];
            //位置的数 不等于 index+1
            while (valueError != index + 1) {
                if (arr[valueError - 1] == valueError) {
                    return;
                }
                int temp = arr[valueError - 1];
                arr[valueError - 1] = valueError;
                valueError = temp;
                arr[index] = temp;
            }
        }
    }

    public static class TipAnchor {
        public static int solution1(int start, int end, int a, int b, int c) {
            return process1(start, end, a, b, c);
        }

        public static int process1(int cur, int end, int a, int b, int c) {
            if (cur == end) {
                return 0;
            }
            int i = process1(cur + 1, end, a, b, c) + a;
            int j = process1(cur * 2, end, a, b, c) + b;
            int k = process1(cur - 2, end, a, b, c) + c;
            return Math.min(Math.min(i, j), k);
        }


        public static int solution2(int start, int end, int a, int b, int c) {
            int limitSpent = ((end - start) / 2) * a;
            int res = process2(0, start, end, a, b, c, limitSpent, 2 * end);
            //其实不需要进行比较，因为 返回必定小于等于limitSpent
            return Math.min(res, limitSpent);
        }

        private static int process2(int pre, int cur, int end, int a, int b, int c, int limitSpent, int maxPopularity) {
            if (cur == end) {
                return pre;
            }
            if (pre > limitSpent) {
                return Integer.MAX_VALUE;
            }
            if (cur > maxPopularity) {
                return Integer.MAX_VALUE;
            }
            int minSpent = Integer.MAX_VALUE;
            //点赞
            int i = process2(pre + a, cur + 2, end, a, b, c, limitSpent, maxPopularity);
            if (i != Integer.MAX_VALUE) {
                minSpent = i;
            }
            //送礼
            int j = process2(pre + b, cur * 2, end, a, b, c, limitSpent, maxPopularity);
            if (j != Integer.MAX_VALUE) {
                minSpent = Math.min(j, minSpent);
            }
            //私聊
            int k = process2(pre + c, cur - 2, end, a, b, c, limitSpent, maxPopularity);
            if (k != Integer.MAX_VALUE) {
                minSpent = Math.min(k, minSpent);
            }
            return minSpent;
        }

        public static int solution3(int start, int end, int a, int b, int c) {
            int limitSpent = ((end - start) / 2) * a;
            int maxPopularity = end * 2;
            int[][] dp = new int[limitSpent + 1][maxPopularity + 1];

            for (int pre = 0; pre < dp.length; pre++) {
                for (int cur = 0; cur < dp[pre].length; cur++) {
                    if (cur == start) {
                        dp[pre][start] = pre;
                    } else {
                        dp[pre][end] = Integer.MAX_VALUE;
                    }
                }
            }
            for (int pre = 0; pre < dp.length; pre++) {
                for (int cur = 0; cur < dp[pre].length; cur++) {
                    //点赞花钱小于平凡解
                    if (pre + a < limitSpent && cur - 2 > 0) {
                        //点赞提升人气 和 当前的花费 取小
                        dp[pre][cur] = Math.min(dp[pre + a][cur - 2], dp[pre][cur]);
                    }
                    //送礼
                    //因为初始人气为偶数，人气为2如果是送礼增长的那么初始为1 不符合题意
                    if (cur % 2 == 0) {
                        //送礼的花费小于平凡解，且当前人气大于2
                        //因为初始人气为偶数，人气为2如果是送礼增长的那么初始为1 不符合题意
                        if (pre + b < limitSpent && cur / 2 > 0) {
                            dp[pre][cur] = Math.min(dp[pre + a][cur / 2], dp[pre][cur]);
                        }
                    }
                    //私聊
                    //私聊之前的人气值 是有效的 且 小于平凡解
                    if (cur + 2 < maxPopularity && pre + c < limitSpent) {
                        //私聊省钱 还是之前的省钱
                        dp[pre][cur] = Math.min(dp[pre + c][cur + 2], dp[pre][cur]);
                    }
                }
            }
            return dp[0][start];
        }

    }


}
